﻿#include "template_multivector.h"

template <typename T>
bool less(T a, T b)
{
	return a < b;
}

template <typename T>
bool more(T a, T b)
{
	return a > b;
}


//bubble sort
template <typename T>
void bubbleSort(TemplateVector<T>& unsort, bool (*compare)(T a, T b))
{
	for (int i = 0; i < unsort.size() - 1; i++)
	{
		bool flag = false;

		for (int j = 0; j < unsort.size() - i - 1; j++)
		{
			if (compare(unsort[j], unsort[j + 1]))
			{
				std::swap(unsort[j], unsort[j + 1]);
				flag = true;
			}
		}
		if (!flag)
			break;
	}
}


//Heap Sort

// вспомогательная функция Heap Sort
template <typename T>
void heapify(TemplateVector<T>& arr, int lenght, int index, bool (*compare)(T a, T b))
{

	int largest = index;
	int left = 2 * index + 1;
	int right = 2 * index + 2;

	if (left < lenght && compare(arr[left], arr[largest]))
		largest = left;

	if (right < lenght && compare(arr[right], arr[largest]))
		largest = right;
	

	if (largest != index)
	{
		std::swap(arr[index], arr[largest]);
		heapify(arr, lenght, largest, compare);
	}
}

// основная функция Heap Sort
template <typename T>
void heapSort(TemplateVector<T>& arr, bool (*compare)(T a, T b))
{
	for (int i = arr.size() / 2 - 1; i >= 0; --i)
		heapify(arr, arr.size(), i, *compare);

	for (int i = arr.size() - 1; i >= 0; --i)
	{
		std::swap(arr[0], arr[i]);
		heapify(arr, i, 0, *compare);
	}

}


// QuickSort сортировка

// 2) вспомогательная функция, которая делит массив на две отсортированные части, которые соритруются относительно pivot
template <typename T>
int partition(TemplateVector<T>& list, int start, int pivot, bool (*compare)(T a, T b))
{
	int i = start;

	while (i < pivot)
	{
		if (compare(list[i], list[pivot]) && i == pivot - 1)
		{
			std::swap(list[i], list[pivot]);
			--pivot;
		}
		else if (compare(list[i], list[pivot]))
		{
			std::swap(list[pivot - 1], list[pivot]);
			std::swap(list[i], list[pivot]);
			--pivot;
		}
		else
			++i;
	}

	return pivot;
}
// 1) основная функция с помощью рекурсии левой и правой части массива
template <typename T>
void quickSortInternal(TemplateVector<T>& list, int start, int end, bool (*compare)(T a, T b))
{
	if (start < end)
	{
		int pivot = partition(list, start, end, compare);

		quickSortInternal(list, start, pivot - 1, compare);
		quickSortInternal(list, pivot + 1, end, compare);
	}
}

template <typename T>    // внешняя оболочка, чтобы унифицировать с другими сортировками для подсчёта времени
void quickSort(TemplateVector<T>& list, bool (*compare)(T a, T b))
{
	quickSortInternal(list, 0, list.size() - 1, compare);
}



//спираль
template<typename T>
void spiral(TemplateMultiVector<T>& matrix)
{
	int top = 0;
	int bottom = matrix.rowsCount() - 1;
	int left = 0;
	int right = matrix.colsCount() - 1;
	int startValue = 1;

	while (top <= bottom && left <= right)
	{
		for (int i = left; i <= right; i++)
			matrix[top][i] = startValue++;
		top++;

		for (int i = top; i <= bottom; i++)
			matrix[i][right] = startValue++;
		right--;

		if (top <= bottom)
			for (int j = right; j >= left; j--)
				matrix[bottom][j] = startValue++;
		bottom--;

		if (left <= right)
			for (int i = bottom; i >= top; i--)
				matrix[i][left] = startValue++;
		left++;
	}
}


// змейка по диагонали
template<typename T>
void fillMatrix(TemplateMultiVector<T>& matrix)
{
	int maxValue = matrix.colsCount() * matrix.rowsCount();
	int startValue = 1;
	int rowIndex = 0;
	int colIndex = 0;

	matrix[rowIndex][colIndex] = startValue;
	++colIndex;
	++startValue;

	while (startValue != maxValue)
	{
		while ((rowIndex != matrix.rowsCount() - 1 || colIndex != matrix.colsCount() - 1) && startValue != maxValue)
		{
			if ((colIndex == 0 && rowIndex == matrix.rowsCount() - 1) || rowIndex == matrix.rowsCount() - 1)
			{
				matrix[rowIndex][colIndex++] = startValue++;
				break;
			}
			else if (colIndex == 0)
			{
				matrix[rowIndex++][colIndex] = startValue++;
				break;
			}
			else
				matrix[rowIndex++][colIndex--] = startValue++;
		}

		while ((rowIndex >= 0 || colIndex <= matrix.colsCount() - 1) && startValue != maxValue)
		{
			if ((rowIndex == 0 && colIndex == matrix.colsCount() - 1) || colIndex == matrix.colsCount() - 1)
			{
				matrix[rowIndex++][colIndex] = startValue++;
				break;
			}
			else if (rowIndex == 0)
			{
				matrix[rowIndex][colIndex++] = startValue++;
				break;
			}
			else
				matrix[rowIndex--][colIndex++] = startValue++;
		}
	}
	matrix[rowIndex][colIndex] = startValue;
}